# search.py
# ---------
# Licensing Information:  You are free to use or extend these projects for
# educational purposes provided that (1) you do not distribute or publish
# solutions, (2) you retain this notice, and (3) you provide clear
# attribution to UC Berkeley, including a link to http://ai.berkeley.edu.
# 
# Attribution Information: The Pacman AI projects were developed at UC Berkeley.
# The core projects and autograders were primarily created by John DeNero
# (denero@cs.berkeley.edu) and Dan Klein (klein@cs.berkeley.edu).
# Student side autograding was added by Brad Miller, Nick Hay, and
# Pieter Abbeel (pabbeel@cs.berkeley.edu).


"""
In search.py, you will implement generic search algorithms which are called by
Pacman agents (in searchAgents.py).
在 search.py 中,您将实现由 Pacman 代理调用的通用搜索算法（在 searchAgents.py 中）。
"""

import util

class SearchProblem:
    """
    This class outlines the structure of a search problem, but doesn't implement
    any of the methods (in object-oriented terminology: an abstract class).

    You do not need to change anything in this class, ever.

    此类概述了搜索问题的结构,但不实现任何方法（在面向对象的术语中：抽象类）。
    您永远不需要更改此类中的任何内容。
    """

    def getStartState(self):
        """
        Returns the start state for the search problem.
        返回搜索问题的开始状态。
        """
        util.raiseNotDefined()

    def isGoalState(self, state):
        """
          state: Search state
          状态：搜索状态

        Returns True if and only if the state is a valid goal state.
        当且仅当状态是有效的目标状态时,返回 True。
        """
        util.raiseNotDefined()

    def getSuccessors(self, state):
        """
          state: Search state

        For a given state, this should return a list of triples, (successor,
        action, stepCost), where 'successor' is a successor to the current
        state, 'action' is the action required to get there, and 'stepCost' is
        the incremental cost of expanding to that successor.
        对于给定的状态,这应该返回一个三元组列表(后继者,操作,stepCost),其中“后继者”是当前
        状态,“操作”是到达那里所需的操作,“stepCost”是扩展到该继任者的增量成本。
        """
        util.raiseNotDefined()

    def getCostOfActions(self, actions):
        """
        actions: A list of actions to take

        This method returns the total cost of a particular sequence of actions.
        The sequence must be composed of legal moves.

        操作：要执行的操作列表

        此方法返回特定操作序列的总成本。序列必须由合法动作组成。
        """
        util.raiseNotDefined()


def tinyMazeSearch(problem):
    """
    Returns a sequence of moves that solves tinyMaze.  For any other maze, the
    sequence of moves will be incorrect, so only use this for tinyMaze.
    返回解决微小迷宫的一系列移动。 对于任何其他迷宫，移动顺序将不正确，因此仅将其用于微小迷宫。
    """
    from game import Directions
    s = Directions.SOUTH
    w = Directions.WEST
    return  [s, s, w, s, w, w, s, w]

def depthFirstSearch(problem):
    """
    Search the deepest nodes in the search tree first.
    首先搜索搜索树中最深的节点。

    Your search algorithm needs to return a list of actions that reaches the
    goal. Make sure to implement a graph search algorithm.
    您的搜索算法需要返回达到目标。确保实现图形搜索算法。

    To get started, you might want to try some of these simple commands to
    understand the search problem that is being passed in:
    要开始使用，您可能需要尝试以下一些简单的命令来了解传入的搜索问题：


    print("Start:", problem.getStartState())
    print("Is the start a goal?", problem.isGoalState(problem.getStartState()))
    print("Start's successors:", problem.getSuccessors(problem.getStartState()))
    """
    "*** YOUR CODE HERE ***"

    '''------------------------------------3------------------------------------'''
    stack = util.Stack()                                # 深度搜索选择栈
    visited_list = []                                   # 初始化一个空集合来存储已访问过的状态
    stack.push((problem.getStartState(), []))           # 把初始状态和空路径压入栈中
    while not stack.isEmpty():                          # 当栈不为空时循环
        cur_node, actions = stack.pop()                 # 弹出栈顶元素
        if problem.isGoalState(cur_node):               # 如果当前状态是目标状态，则返回路径
            print(actions)                              #查看运行方向记录
            return actions
        if cur_node not in visited_list:                # 如果当前状态没有被访问过
            expand = problem.getSuccessors(cur_node)
            visited_list.append(cur_node)               #则标记为已访问，并遍历其后继状态
            for location, direction, cost in expand:    # ((5, 4), 'South', 1)
                if (location not in visited_list):
                    stack.push((location, actions + [direction]))
        

    # '''------------------------------------2------------------------------------'''
    # cur_state = problem.getStartState() #搜索问题的开始状态。
    # close_set = set()                   #保存所有已经探索过的位置的集合
    # stack = util.Stack()                #初始化一个空栈
    # result_list = []                    #结果列表
    # stack.push((cur_state, []))         #把初始状态和空路径压入栈中
    # while(not problem.isGoalState(cur_state)):  #在找到终点前一直搜索,当且仅当状态是有效的目标状态时,返回 True。
    #     cur_node = stack.pop()                  
    #     close_set.add(cur_node[0])
    #     successor = problem.getSuccessors(cur_node[0])
    #     for i in successor:
    #         print(i)                    # ((5, 4), 'South', 1)
    #         if not i[0] in close_set:   #判断i是否已经探索过
    #             stack.push((i[0], cur_node[1] + [i[1]]))
    #         cur_state = i[0]
    #     result_list = cur_node[1] + [i[1]]
    #     print(result_list)            #它的走向的结果列表
    # return result_list
    
    '''------------------------------------1------------------------------------'''
    # result_list = []                    #结果列表
    # close_set = set()                   #保存所有已经探索过的位置的集合
    # stack = util.Stack()                #保存当前探索路径的栈，节点为三元组successor
    # cur_state = problem.getStartState() #搜索问题的开始状态。
    # cur_node = (cur_state,'Start',0)
    # close_set.add(cur_state)
    # stack.push(cur_node)                #将“项目”推送到堆栈上

    # while(True):                        #如果堆栈为空，则返回true
    #     cur_node = stack.pop()          #获取栈顶节点
    #     cur_state = cur_node[0]         #栈顶节点的位置
    #     if(problem.isGoalState(cur_state)):     #栈顶节点是终点，则将栈倒转，所得列表即为答案.当且仅当状态是有效的目标状态时,返回 True。
    #         result_list.append(cur_node[1])
    #         while(not stack.isEmpty()): #如果堆栈不为空
    #             i = stack.pop()
    #             result_list.append(i[1])
    #         result_list.pop()           #从堆栈中弹出最近推送的项目
    #         result_list.reverse()
    #         print("result list:",result_list)
    #         break
    #     else:                           #否则，获取栈顶节点的后继节点，并遍历
    #         cur_successors = problem.getSuccessors(cur_state)
    #         for i in cur_successors:            
    #             if i[0] in close_set:   #若遍历到的后继节点已经探索过，则跳过
    #                 print("node:",i,"has been explored.")
    #                 continue    
    #             else:                   #若遍历到的后继节点未探索，则将其压入栈中，开始下一轮循环
    #                 print("node:",i,"is added to the stack.")
    #                 close_set.add(i[0]) #已经探索过的位置的集合
    #                 stack.push(cur_node)
    #                 stack.push(i)
    #                 break
    # print("result list:",result_list)   #它的走向的结果列表
    # print("cost:",problem.getCostOfActions(result_list))
    # return result_list



    # util.raiseNotDefined()


def breadthFirstSearch(problem):
    """Search the shallowest nodes in the search tree first.'''
    '''首先搜索搜索树中最浅的节点"""
    "*** YOUR CODE HERE ***"
    queue = util.Queue()                                # 深度搜索选择队列
    visited_list = []                                   # 初始化一个空集合来存储已访问过的状态
    queue.push((problem.getStartState(), []))           # 把初始状态和空路径压入队列中
    while not queue.isEmpty():                          # 当队列不为空时循环
        cur_node, actions = queue.pop()                 # 弹出队列顶元素
        if problem.isGoalState(cur_node):               # 如果当前状态是目标状态，则返回路径
            print(actions)                              #查看运行方向记录
            return actions
        if cur_node not in visited_list:                # 如果当前状态没有被访问过
            expand = problem.getSuccessors(cur_node)
            visited_list.append(cur_node)               #则标记为已访问，并遍历其后继状态
            for location, direction, cost in expand:    # ((5, 4), 'South', 1)
                if (location not in visited_list):
                    queue.push((location, actions + [direction]))

    # util.raiseNotDefined()

def uniformCostSearch(problem):
    """Search the node of least total cost first.'''
    '''首先搜索总成本最低的节点"""
    "*** YOUR CODE HERE ***"

    '''
    result_list = []                                        #结果列表
    priority_queue = util.PriorityQueue()                   #实现优先级队列数据结构
    prenode_dict = {}                                       #父节点字典，prenode_dict[state]表示state的父节点信息
    cur_state = problem.getStartState()                     #获得初始状态位置
    # print(cur_state)                         #(34, 16)
    cur_node = (cur_state,'Start',0)           #cur_node: ((34, 16), 'Start', 0)
    priority_queue.push(cur_state,0)
    prenode_dict[cur_state] = cur_node         #prenode_dict: {(34, 16): ((34, 16), 'Start', 0), ...}
    while(True):
        cur_state = priority_queue.pop()                    #优先队列出队
        cur_node = prenode_dict[cur_state]
        # print("current position:",cur_state)    #current position: (24, 6)
        # print("cur_node:",cur_node)             #cur_node: ((24, 5), 'North', 66)
        if(problem.isGoalState(cur_state)):                 #当前节点是终点，则根据父节点字典回推得到路径
            print("\n搜索完成")
            while(cur_node[0] != problem.getStartState()): 
                result_list.append(cur_node[1])
                # print(cur_node, " 的预节点是 ", prenode_dict[cur_node[0]])
                cur_node = prenode_dict[cur_node[0]]
            result_list.append(cur_node[1])                 #将第一步加进结果列表
            result_list.reverse()                           #结果列表倒转，得到答案
            break            
        cur_successors = problem.getSuccessors(cur_state)   #当前节点不是终点，则获取后继节点
        for i in cur_successors:                            #遍历后继节点，若某一后继节点已经在父节点字典的key中，则根据代价值更新优先队列
            if(i[0] in prenode_dict):                      
                if(i[2] + prenode_dict[cur_state][2] < prenode_dict[i[0]][2]):
                    prenode_dict[i[0]][1] = i[1]
                    prenode_dict[i[0]][2] = i[2] + prenode_dict[cur_state][2]
                    priority_queue.update(i[0],prenode_dict[i[0]][2])
                    # print(i," 已更新 ")
                else:
                    continue
            else:                                           #若该节点不在父节点字典的key中，即该节点没有探索过
                prenode_dict[i[0]] = (cur_state,i[1],i[2] + prenode_dict[cur_state][2])
                priority_queue.update(i[0],prenode_dict[i[0]][2])
                # print(i," 已添加至优先级队列")
    print("最终前进路线为：", result_list)
    return result_list
    '''

    close_set = set()                      #创建一个空集合，保存已经探索过的位置。
    queue = util.PriorityQueue()           #创建一个优先队列，用来存储待探索的位置和对应的动作序列。
    queue.push((problem.getStartState(), []) ,0)           #将初始状态和空动作序列压入队列，并给它们一个0的优先级。
    result_list = []                       #初始化一个空集合来存储已访问过的状态
    while(True):                           #查找目标状态或者队列为空为止
        cur_node = queue.pop()             #从队列中弹出一个元素
        # print("cur_node:",cur_node)      # ((1, 1), ['West', 'West',...])
        # print("close_set:",close_set)    # {(34, 7), (16, 6),...}
        result_list = cur_node[1]          #将当前动作序列赋值给result_list变量。
        if problem.isGoalState(cur_node[0]):               #判断当前位置是否是目标状态。
            return result_list             #如果是目标状态，则返回当前动作序列并结束循环。
        if cur_node[0] not in close_set:                   #如果当前位置不在已探索集合中
            successors = problem.getSuccessors(cur_node[0])#获取当前位置的所有后继位置，并赋值给successors变量。
            # print("successors:",successors) # [((13, 6), 'North', 1), ((13, 4), 'South', 1)]
            for i in successors:           #遍历所有后继位置
                if i[0] not in close_set:  #如果后继位置不在已探索集合中         #
                    new_actions = result_list + [i[1]]      #将后继位置所需的动作添加到当前动作序列中，并赋值给new_actions变量。
                    # print("new_actions:",new_actions)
                    queue.update((i[0], result_list + [i[1]]), problem.getCostOfActions(new_actions))           
                    #将后继位置和新动作序列更新到队列中，并根据新动作序列所需的总代价设置优先级。如果队列中已经有相同的后继位置，则只保留代价最小的那个。
        close_set.add(cur_node[0])         #将当前位置添加到已探索集合中。
    return result_list                     # 如果队列为空，则返回空列表并结束循环。

    # util.raiseNotDefined()

def nullHeuristic(state, problem=None):
    """
    A heuristic function estimates the cost from the current state to the nearest
    goal in the provided SearchProblem.  This heuristic is trivial.
    启发式函数估计从当前状态到提供的搜索问题中最接近目标的成本。 这种启发式是微不足道的。
    """
    return 0

def aStarSearch(problem, heuristic=nullHeuristic):
    """Search the node that has the lowest combined cost and heuristic first.首先搜索组合成本最低且启发式的节点。"""
    "*** YOUR CODE HERE ***"

    cur_state = problem.getStartState()                     # 设置初始状态
    close_set = set()                                       # 保存所有已经探索过的位置  {(34, 7), (16, 6),...}
    queue = util.PriorityQueue()                            # 用优先队列存储待探索的位置和相应的动作序列
    queue.push((cur_state, []) ,nullHeuristic(cur_state,problem)) # 使用nullHeuristic函数计算其优先级
    result_list = []                                        # 初始化一个空集合来存储已访问过的状态
    while(True):                                            # 直到找到目标状态或者队列为空为止
        cur_node = queue.pop()          # ((1, 1), ['West', 'West',...])
        result_list = cur_node[1] 
        if problem.isGoalState(cur_node[0]):                # 判断当前状态是否是问题的目标状态
            return result_list                              # 是则返回result_list
        if cur_node[0] not in close_set:                    # 不是则判断当前状态是否已经在close_set中
            successors = problem.getSuccessors(cur_node[0]) # 如果不在，则获取当前状态的所有后继状态。
            for i in successors:                            # 对于每个后继状态
                if i[0] not in close_set:                   # 判断后继状态是否已经在close_set中
                    new_actions = result_list + [i[1]]      # 如果不在close_set中，则将后继状态对应的动作添加到result_list中，形成新的动作序列，并赋值给new_actions变量
                    new_cost = problem.getCostOfActions(new_actions) + heuristic(i[0], problem) 
                    # 计算新动作序列所需的总代价，并加上启发式函数heuristic对后继状态进行评估，得到新优先级，并赋值给new_cost变量
                    queue.update((i[0], result_list + [i[1]]), new_cost) 
                    # 将后继状态和新动作序列以及新优先级更新到队列中。如果队列中已经存在相同的后继状态，则根据优先级选择保留哪个版本；如果不存在，则直接添加到队列中。
            close_set.add(cur_node[0])                      # 将当前状态添加到已经探索过
    return result_list

    # util.raiseNotDefined()


# Abbreviations
bfs = breadthFirstSearch
dfs = depthFirstSearch
astar = aStarSearch
ucs = uniformCostSearch
